package com.arron.algorithm.leetcodetop100.二分查找;

public class x的平方根 {



    public int mySqrt(int x) {

        if (x  == 0){
            return 0;

        }

        if (x<4){
            return 1;
        }
        // 当x >=4的时候，有 (x/2)2 >= x
        int left = 2;
        int right = x/2;


        while (left<=right){


            int mid = left + (right-left)/2 ;

            if (mid*mid >x){
                right = mid -1;
            }else if (mid * mid < x){
                left = mid+1;
            }else {
                return mid;
            }
        }

        return right;

    }

}
